package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * KthSmallest
 *
 * 230. 二叉搜索树中第K小的元素
 *
 * @author: lupeng6
 * @create: 2021/1/28 14:45
 */
public class KthSmallest {

    public static void main(String[] args) {

    }

    /**
     * 中序遍历二叉搜索树, 找到指定节点
     *
     * @author lupeng6
     * @date 2021/1/28 14:45
     */
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        this.k = k;
        inOrder(root);
        return result.get(k - 1);
    }

    private List<Integer> result = new ArrayList<>();

    private int k;

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        if (result.size() > k) {
            return;
        }
        inOrder(node.left);
        result.add(node.val);
        inOrder(node.right);
    }
}
